#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/**
 * 最大公约数（欧几里得算法）：对应Python的gcd函数
 */
int gcd(int m, int n) {
    if (m < n) {
        // 交换m和n（C语言无Python的元组交换，用临时变量）
        int temp = m;
        m = n;
        n = temp;
    }
    while (m % n != 0) {
        int temp = m;
        m = n;
        n = temp % n;
    }
    return n;
}

/**
 * 二进制快速幂：计算 (base^power) 的结果（不直接取模，后续统一取模）
 * 对应Python的binary_exponentiation函数
 */
long long binary_exponentiation(long long base, long long power) {
    long long power_2 = 1;
    long long r = 1;
    long long p = base;
    while (power_2 <= power) {
        if ((power_2 & power) != 0) { // 按位与判断当前位是否为1
            r *= p;
        }
        p *= p;           // 底数平方
        power_2 <<= 1;    // power_2 *= 2（左移1位）
    }
    return r;
}

/**
 * 欧拉函数 φ(n)：计算1~n中与n互质的整数个数
 * 对应Python的euler_totient函数（筛法实现）
 */
int euler_totient(int n) {
    if (n <= 0) {
        fprintf(stderr, "错误：欧拉函数的参数n必须为正整数！\n");
        return -1;
    }
    // 初始化phi数组：phi[i] = i（对应Python的 [i for i in range(n+1)]）
    int *phi = (int *)malloc((n + 1) * sizeof(int));
    if (!phi) {
        fprintf(stderr, "错误：内存分配失败！\n");
        return -1;
    }
    for (int i = 0; i <= n; i++) {
        phi[i] = i;
    }

    // 筛法计算欧拉函数：对应Python的双重循环
    for (int i = 1; i <= n; i++) {
        // j从2*i开始，步长为i（对应Python的 range(i<<1, n+1, i)）
        for (int j = i << 1; j <= n; j += i) {
            phi[j] -= phi[i];
        }
    }

    int result = phi[n];
    free(phi); // 释放临时数组
    return result;
}

/**
 * 模乘逆元：基于欧拉定理 a^(φ(m)-1) ≡ a^(-1) mod m（a和m互质）
 * 对应Python的modular_inverse函数
 * @return: 成功返回逆元（正整数）；失败返回-1（并打印错误信息）
 */
int modular_inverse(int a, int m) {
    // 第一步：判断a和m是否互质
    if (gcd(a, m) != 1) {
        fprintf(stderr, "RuntimeError: %d,%d不互质，没有模乘逆元\n", a, m);
        return -1;
    }

    // 第二步：计算欧拉函数 φ(m)
    int phi_m = euler_totient(m);
    if (phi_m == -1) {
        return -1; // 欧拉函数计算失败
    }

    // 第三步：二进制快速幂计算 a^(phi_m - 1) mod m
    // 用long long避免溢出（a和phi_m较大时，中间结果可能超出int范围）
    long long base = (long long)a;
    long long power = (long long)(phi_m - 1);
    long long exp_result = binary_exponentiation(base, power);
    int inverse = (int)(exp_result % m);

    // 确保逆元为正（若mod结果为0，实际逆元是m，但互质场景下不会出现）
    return inverse < 0 ? inverse + m : inverse;
}

// 测试主函数
int main() {
    // 测试用例1：a=3, m=2（对应Python第一个测试）
    int a1 = 3, m1 = 2;
    int inv1 = modular_inverse(a1, m1);
    if (inv1 != -1) {
        printf("%d * %d %% %d = %d\n", a1, inv1, m1, (a1 * inv1) % m1);
    }

    // 测试用例2：a=1024, m=997（对应Python第二个测试）
    int a2 = 1024, m2 = 997;
    int inv2 = modular_inverse(a2, m2);
    if (inv2 != -1) {
        printf("%d * %d %% %d = %d\n", a2, inv2, m2, (1LL * a2 * inv2) % m2);
        // 注：1LL强制转换为long long，避免a2*inv2溢出（1024*517=529408，未超int但保险）
    }

    // 测试用例3：a=3, m=6（不互质，预期报错）
    int a3 = 3, m3 = 6;
    int inv3 = modular_inverse(a3, m3);
    if (inv3 != -1) {
        printf("%d * %d %% %d = %d\n", a3, inv3, m3, (a3 * inv3) % m3);
    }

    return 0;
}